1. Field of the Invention
The present invention relates to digital filtering methods and devices.
It finds an advantageous application to the filtering of digital images, in particular for the compression of images in accordance with “JPEG 2000”, currently being drafted.
2. Description of the Related Art
Two techniques are notably known for implementing the filtering of digital signals using wavelet filters:
filtering by convolution, and
filtering by “lifting”.
A few elementary concepts on wavelet filters, and then on lifting, are given below.
It is known that the wavelet filtering of a monodimensional signal Xi can be defined as:
the convolution of a low-pass filter H0(k) with the signal Xi, the signal Yn resulting from the convolution being downsampled by a factor of two:
                              Y                      2            ⁢            n                          =                              ∑            k                    ⁢                                                    H                0                            ⁡                              (                k                )                                      ·                          X                                                2                  ⁢                  n                                -                k                                                                        (        1        )            and
the convolution of a high-pass filter H1(k) with the signal Xi, the signal Yn resulting from the convolution being downsampled by a factor of two:
                              Y                                    2              ⁢              n                        +            1                          =                              ∑            k                    ⁢                                                    H                1                            ⁡                              (                k                )                                      ·                          X                                                2                  ⁢                  n                                +                1                -                k                                                                        (        2        )            
The result of the filtering, referred to as a wavelet filtering operation (H0, H1), produces a signal Yi, in which each even-indexed sample Y2n is a low-pass coefficient and each odd-indexed odd-indexed sample Y2n+1 is a high-pass coefficient.
The low-pass filter and the high-pass filter must satisfy certain conditions, referred to as perfect reconstruction conditions, so that the perfect reconstruction of the signal Xi from the signal Yi is possible.
If the notation of the z transform is used for the finite impulse response filters, namely
                                                        H              i                        ⁡                          (              z              )                                =                                    ∑              k                        ⁢                                                            H                  i                                ⁡                                  (                  k                  )                                            ·                              z                                  -                  k                                                                    ,                            (        3        )            then the perfect reconstruction condition which the filters must satisfy is:H0(z).H1(−z−1)+H0(−z).H1(z−1)=2.  (4)
It is known that some wavelet filters have symmetry properties.
An odd-length symmetric wavelet filter H(k) or WSS (Whole-Sample Symmetric) filter is defined by the following equation, referred to as WSS symmetry, between all the coefficients of the filter:∀k, H(−k)=H(k)  (5)
An even-length symmetric wavelet filter or HSS (Half-Sample Symmetric) filter is defined by the following equation, referred to as HSS symmetry, between all the coefficients of the filter:∀k, H(−k)=H(k+1).  (6)
An even-length antisymmetric wavelet filter or HSA (Half-Sample Antisymmetric) filter is defined by the following equation, referred to as HSA symmetry, between all the coefficients of the filter:∀k, H(−k)=−H(k+1).  (7)
The technique of lifting, mentioned above, consists of implementing a filtering step by decomposing it into an equivalent sequence of elementary filtering operations, referred to as lifting steps. This decomposition is referred to as lifting factorisation. For more details on lifting factorisation, reference can usefully be made to the article by Ingrid DAUBECHIES and Wim SWELDENS entitled “Factoring wavelet transforms into lifting steps”, in J. Fourier Anal. Appl., vol. 4, No. 3, pages 247 to 269, 1998.
It should be stated in particular that, when a filtering operation is performed in the form of lifting steps, in order to transform a signal Xi into a signal Yi, it is generally begun by copying all the samples of the signal Xi into the signal Yi (i.e. Yi=Xi), and then the even-indexed samples and the odd-indexed samples of the signal Yi are modified alternately.
There are two types of lifting step:
high-pass lifting steps, and
low-pass lifting steps.
A high-pass lifting step consists of modifying odd-indexed samples by adding to them a sample function of even-indexed samples which are weighted or filtered:
                              ∀          n                ,                              Y                                          2                ⁢                n                            +              1                                =                                    Y                                                2                  ⁢                  n                                +                1                                      +                          R              ⁡                              (                                                      ∑                    k                                    ⁢                                                            a                      k                                        ·                                          Y                                                                        2                          ⁢                          n                                                +                                                  2                          ⁢                          k                                                                                                                    )                                                                        (        8        )            
The function R is, in general terms, any approximation of the variable x. The function R can be a rounding operator which rounds a real value x to an integer (such as the closest integer), or can simply be identity: R(x)=x.
A low-pass lifting step consists of modifying even-indexed samples (low-pass) by adding to them a function of odd-indexed samples which are weighted or filtered:
                              ∀          n                ,                              Y                          2              ⁢              n                                =                                    Y                              2                ⁢                n                                      +                          R              ⁡                              (                                                      ∑                    k                                    ⁢                                                            b                      k                                        ·                                          Y                                                                        2                          ⁢                          n                                                +                                                  2                          ⁢                          k                                                +                        1                                                                                            )                                                                        (        9        )            
In the case where R(x)=x, at each lifting step, each low-pass sample Y2n can be expressed in the form of a linear combination of samples of the signal Xi, corresponding to a low-pass filtering of the signal Xi. Thus each low-pass lifting step can be associated with a low-pass filter.
It is said that each low-pass lifting step lifts a low-pass filter (one which is associated with the previous low-pass lifting step) into another low-pass filter (the one which is associated with the current low-pass lifting step). The term lifting accounts for the fact that the support of the resulting low-pass filter (that is to say the number of coefficients of the filter) is greater than that of the corresponding low-pass filter at the previous step. The low-pass filter with the larger support finally obtained by lifting is called the “equivalent low-pass filter”.
The same applies to the high-pass filters and the lifting steps, that is to say each high-pass lifting step can be seen as the lifting of a high-pass filter into a high-pass filter with a larger support, referred to as the “equivalent high-pass filter”.
The same terminology is used in the case where the approximation function R is not identity.
Thus the lifting-based implementation of a wavelet filtering operation (H0, H1) can be seen as a sequence of operations during which, alternately and iteratively, low-pass filters are lifted into equivalent low-pass filters with a larger support, and high-pass filters are lifted into equivalent high-pass filters with a larger support, until the low-pass filter is equal to H0 and the high-pass filter is equal to H1.
Several types of symmetry are also encountered in the lifting steps:                there are two types of symmetric lifting steps:                    lifting steps with WSS symmetry, and            lifting steps with HSS symmetry; and                        there are two types of antisymmetric lifting steps:                    lifting steps with WSA antisymmetry, and            lifting steps with HSA antisymmetry.                        
An odd-length symmetric lifting or WSS lifting (“Whole-Sample Symmetric lifting”) step is defined by a WSS symmetry relationship between the filtering coefficients of the lifting step:a−k=ak  (10)
An even-length symmetric lifting or HSS lifting (“Half-Sample Symmetric lifting”) step is defined by an HSS symmetry relationship between the filtering coefficients of the lifting step:a−k=ak−1  (11)
An odd-length antisymmetric lifting or WSA lifting (“Whole-Sample Antisymmetric lifting”) step is defined by a WSA symmetry relationship between the filtering coefficients of the lifting step:a0=0 and a−k=−ak  (12)
An even-length antisymmetric lifting or HSA lifting (“Half-Sample Antisymmetric lifting”) step is defined by an HSA symmetry relationship between the filtering coefficients of the lifting step:a−k=−ak−1  (13)
A single-coefficient lifting or SC lifting (“Single-Coefficient lifting”) step is defined by the fact that all the filtering coefficients of the lifting step except one (denoted ak′) are zero.
For the low-pass lifting steps,
if k′=0, the lifting step is called a Right-side Single Coefficient low-pass lifting or RSC low-pass lifting step, and
if k′=−1, the lifting step is called a Left-side Single Coefficient low-pass lifting or LSC low-pass lifting step.
In a similar manner, for the high-pass lifting steps,
if k′=1, the lifting step is called a Right-side Single Coefficient high-pass lifting or RSC high-pass lifting step, and
if k′=0, the lifting step is called a Left-side Single Coefficient high-pass lifting or LSC high-pass lifting step.
Given that, at the present time, more and more signal compression algorithms use wavelet filtering operations for the decorrelation of the signals, it is very interesting to have available an effective implementation of these filtering operations. Various image compression algorithms use bidimensional wavelet transformations, which consist of the successive application of monodimensional transformations of the type described in the introduction.
An effective implementation of wavelet-based monodimensional filtering is lifting-based filtering.
It is known in fact that lifting-based filtering reduces the number of filtering operations (multiplications and additions) and also affords a reversible implementation of wavelet-based filtering, that is to say with perfect reconstruction of the signal, without loss of information, in the case of signals whose sample values are integer.
In addition, the step which is the reverse of a lifting step is obtained in a trivial fashion by changing the sign before the approximation function R given in equations (8) and (9) above. This makes it possible notably to use the same circuitry in a hardware implantation corresponding to both forward and reverse wavelet transformations.
For a given pair of wavelet filters (H0,H1) the problem consists of finding a sequence of lifting steps which will implement the wavelet transformation. This is the problem of lifting factorisation.
Two families of wavelet filters are known which have good signal decorrelation properties: the family WSS/WSS, abbreviated to WSS, and the family HSS/HSA, the notation A/B meaning that the low-pass filter H0 has a symmetry A and the high-pass filter H1 has a symmetry B.
The problem consisting of implementing WSS wavelet filters by using HSS lifting steps has been resolved and is described in the article by Ingrid DAUBECHIES and Wim SWELDENS cited above.
The problem consisting of implementing HSS/HSA wavelet filters has been partly resolved, by using WSA lifting steps.
However, this solution is only partial since this implementation of the prior art applies only to a limited set of HSS/HSA wavelet filters and not to all of these filters.
Moreover, the publication by E. MAJANI entitled “Low-complexity wavelet filter design for image compression”, TDA Progress Report 42–119, NASA Jet Propulsion Laboratory, Pasadena, Calif., 15 Nov. 1994, indicates that it is possible to use WSA lifting steps for lifting a pair of filters (H0,H1), where the two filters have the same support, into a pair of filters with a larger support (H′0,H′1). However, no indication is found therein about the way of implementing, by lifting steps, pairs of filters (H0,H1) where the two filters have the same support and where this support is greater than two.